Digital cross-connect communications network devices, such as the 1631 SX manufactured by Alcatel Network Systems, Inc., are designed to make connections between input gates on input switches and output gates on output switches. Known designs for such cross-connect devices make use of matrices to connect the input gates to the output gates. To limit the physical space and manufacturing costs of the matrices, designers seek to minimize the number of cross-connects in the matrix. This objective becomes more complicated as market demands for communications services increase. In particular, as network devices address larger markets, the devices must service more and more input and output signals. These factors exacerbate the space and cost limitation problems even more for communications matrix devices.
One matrix configuration that uses a minimal number of matrix cross-connects for a given number of input gates and output gates and that provides a potentially optimal solution is known as a "rearrangeable" matrix. For the rearrangeable matrix, the number of center stage switches must equal or exceed the number of input gates on each input switch of the matrix. In a rearrangeable matrix, there exists a set of conditions such that, although the device does not use all input gates and all output gates, an attempt to use an idle input gate and an output gate is prohibited because existing connections block the signal flow through the matrix. This may happen, for example, if existing connections already occupy at least one link in every possible path between the input and output gates in question.
In a rearrangeable network, it is always possible to unblock a flow path from an idle input gate to an idle output gate by moving existing connections in the network. The term "rearrangeable," therefore, describes the property that for a given state of a network and any given idle pair of input and output gates, the existing connections of the matrix may be reassigned to new paths, if necessary, to connect the idle pair
Existing methods and systems for connecting inputs to outputs in rearrangeable matrices generally use a standard rearrangement technique that determines which cross-connects of the matrix to rearrange to permit a signal to flow. N.C. Paull in "Reswitching of Connection Networks," The Bell System Technical Journal, May, 1962, pp. 833-856, describes this known method for unblocking a rearrangeable matrix. This method (hereinafter referred to as Paull's Method) suffers from a major limitation. Paull's Method requires breaking some of the cross-connects and making some other of the cross-connects to rearrange matrix. This procedure takes time and results in undesirable service delays or interruptions during matrix rearrangement.
It is an object of the present invention, therefore, to provide a method and system that permits immediately connecting idle input gates to idle output gates and, if a rearrangeably blocked condition occurs, rearrange the matrix after the immediate connection. An important aspect of this process is to rearrange the matrix using a minimal number of rearrangements of existing connections. The present invention, therefore, achieves this object with a minimal amount of additional circuitry and avoids the service delays and interruptions of known rearrangement methods and systems.
It is also an object of the present invention to provide a method and system for determining the minimum number of rearrangements for a rearrangeably blocked communications matrix by representing the communications matrix by a square matrix having a first dimension representing the input stage of the communications matrix and a second dimension representing the output stage of the communications matrix so that, in the square matrix, cells represent intersections of the first dimension with the second dimension and indicate possible center stage connections between the input stage and the output stage of the matrix, and wherein the square matrix identifies a blocked center stage switch. A pair of center stage switches, one of which is not associated with the same output stage switch as the blocked center stage switch, and the other of which is not associated with the same input stage switch as the blocked center stage switch, are identified and the number of rearrangement steps necessary for a first rearrangement sequence through the communications matrix from the input stage to the output stage is determined first using one of the center stage switches of the pair and the number for a second rearrangement sequence through the communications matrix from the input stage to the output stage using the other center stage switch is determined. The method performs the rearrangement sequences in incremental parallel steps and ends upon first determining the shorter of the two rearrangement sequences that the pair of center stage switches yields.